package com.springchang.leetcode.array;

/**
 * leetcode :剑指 Offer 53 - II. 0～n-1中缺失的数字
 */
public class MissingNumber_offer53 {

    //用二分查找来解决这道题
    public static int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length-1;

        while(left <= right) {
            int mid = (left+right)/2;
            if(nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid-1;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,1,2,3,4,5,6,7,9};
        System.out.println(String.format("s = %s", missingNumber(nums)));
    }
}
